package Compation;

public class numStepsI {
    public static void main(String[] args) {
        String s = "1101";
        String res = new numStepsI().addOne(s);
        System.out.print(res);
    }

    public int numStepsI(String s) {
        int res = 0;

        if (s == "1") {
            return 0;
        }
        while (s.length() >= 2) {
            if (s.charAt(s.length() - 1) == '1') {
                s = addOne(s);
                res++;

            } else {
                s = s.substring(1, s.length());
                res++;
            }
        }
        return res;
    }

    /**
     * 当最后一位时奇数时，直接加一
     * @param s
     * @return
     */
    private String addOne(String s) {
        char[] data = s.toCharArray();

        int carry = 1;

        for (int i = s.length() - 1; i >= 0; i--) {
            if (carry == 1) {
                if (data[i] == '0') {
                    data[i] = '1';
                    carry = 0;
                } else {
                    data[i] = '0';
                    carry = 1;
                }
            } else {
                break;
            }
        }

        return data.toString();
    }
}
